package com.tping.linked;

/**
 * 双向链表
 */
public class DoublyLinked {

    private LinkedNode first;

    private LinkedNode last;

    private int size;

    public DoublyLinked(){}

    /**
     * 添加元素节点
     * @param val
     */
    public void add(int val, int index){
        if( index < 0 || index > size ){
            throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
        }

        if( size == index ){
            LinkedNode temp = last;
            LinkedNode newNode = new LinkedNode(temp, val, null);
            last = newNode;
            if( temp == null ){
                first = newNode;
            }else{
                temp.next = newNode;
            }
        }else{
            // 获取index节点位置元素
            LinkedNode node = node(index);
            LinkedNode pred = node.prev;
            LinkedNode newNode = new LinkedNode(pred, val, node);
            pred.prev = newNode;
            if( pred == null ){
                first = newNode;
            }else{
                pred.next = newNode;
            }
        }
        size++;
    }

    /**
     * 修改元素节点
     * @param node
     */
    public void update(LinkedNode node, int i){
        LinkedNode temp = first;
        for (;temp != null;){
            if( temp == null ){
                break;
            }
        }
    }

    public int size(){
        return size;
    }

    protected LinkedNode node(int index){
        // 对半分
        if( index < (size >> 1) ){
            LinkedNode l = first;
            for (int i = 0; i < index; i++) {
                l = l.next;
            }
            return l;
        }else{
            LinkedNode l = last;
            for (int i = size - 1; i > index; i--) {
                l = l.prev;
            }
            return l;
        }
    }

    public void show(){
        if( first == null ) return;

        LinkedNode temp = first;
        for (; temp != null ; ) {
            System.out.println(temp);
            temp = temp.next;
        }
    }

    static class LinkedNode{
        public int val;
        public LinkedNode next;
        public LinkedNode prev;

        public LinkedNode(LinkedNode prev, int val, LinkedNode next){
            this.val = val;
            this.prev = prev;
            this.next = next;
        }

        @Override
        public String toString() {
            return "LinkedNode{" +
                    "val=" + val +
                    ", next=" + next +
                    ", prev=" + prev +
                    '}';
        }
    }
}
